package top.lyc829.leetcode.T3;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        if (s.length() < 2) {
            return s.length();
        }


        Set<Character> set = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            set.clear();
            set.add(s.charAt(i));
            int tmpLength = 1;
            for (int j = i + 1; j < s.length(); j++) {
                if (!set.contains(s.charAt(j))) {
                    set.add(s.charAt(j));
                    tmpLength++;
                } else {
                    break;
                }
            }
            if (maxLength < tmpLength) {
                maxLength = tmpLength;
            }
        }

        return maxLength;
    }

    /**
     * 滑动窗口解决
     *
     * @param s 字符串
     * @return 长度
     */
    public int lengthOfLongestSubstring2(String s) {

        int maxLength = 0;
        Set<Character> set = new HashSet<>();

        int r = 0;
        for (int i = 0; i < s.length(); i++) {

            // 每次循环开始，把最左侧的字符去除
            if (i != 0) {
                set.remove(s.charAt(i - 1));
            }

            while (r < s.length() && !set.contains(s.charAt(r))) {
                set.add(s.charAt(r));
                r++;
            }

            if (r - i > maxLength) {
                maxLength = r - i;
            }

        }

        return maxLength;
    }

    public int lengthOfLongestSubstring3(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }


    public static void main(String[] args) {

        Solution s = new Solution();
        int res = s.lengthOfLongestSubstring3("pwwkew");
        System.out.println(res);

    }
}
